/**
 * @param {number[]} nums
 * @return {boolean}
 */
 var canPartition = function(nums) {
    nums.sort((a,b) => a-b);
    let total=nums.reduce((a,b) => a+b);
    if(nums.length==1 || total%2==1) return false;
    let half=total/2;
    function dfs(offset,val){
        let i=offset;
        while(val+nums[i]<half){
            dfs(i+1,val+nums[i]);
            i++;
        }
        if(val+nums[i]==half){
            return true;
        }
        return false
    }
    return dfs(0,0);
};

//超时


/**
 * @param {number[]} nums
 * @return {boolean}
 */
 var canPartition = function(nums) {
    let total=nums.reduce((a,b) => a+b);
    if(nums.length==1 || total%2==1) return false;
    let half=total/2;
    let dp = new Array(half).fill(false);
    dp[0]=true;
    for(let i of nums){
        let j=half;
        while(j>=i){
            dp[j]|=dp[j-i];
            j--;
        }
    }
    return dp[half];
};

//二维DP，背包问题